package algorithm.search.binary.simple;

/**
 * @program: beauty_of_data_structure_and_algotithm
 * @description: a simple int list from small to big without redundence.
 * @author: Keyu Li
 * @create: 2021-09-01 21:55
 **/

public class BinarySearch {
    final static int arr[] = {1, 2, 3, 5, 6, 8, 11, 14, 15, 17, 19, 21, 23, 26, 27, 29, 30};

    public static void main(String[] args) {
        int index;
        int target = 30;
        index = binarySearch(arr, target);
        System.out.println(index);
        index = recurSearch(arr, 0, arr.length - 1, target);
        System.out.println(index);
    }

    private static int binarySearch(int[] arr, int target) {
        int low = 0;
        int high = arr.length - 1;
        int mid = (low + high) >> 1;
        while (low <= high) {
            if (arr[mid] == target)
                return mid;
            else if (arr[mid] < target)
                low = mid + 1;
            else
                high = mid - 1;
            mid = (low + high) >> 1;
        }
        return -1;
    }

    private static int recurSearch(int[] arr, int low, int high, int target) {
        int mid = (low + high) >> 1;
        if (low > high)
            return -1;
        if (arr[mid] == target)
            return mid;
        if (arr[mid] < target)
            return recurSearch(arr, mid + 1, high, target);
        else
            return recurSearch(arr, low, high - 1, target);
    }
}
